package com.practice.niuke.new_direct_basics.class08;

import java.util.ArrayList;
import java.util.List;

/**
 * 打印一个字符串的全部子序列， 包括空字符串
 */
public class Code02_PrintAllSubsquences {

    /**
     * 收集字符串str的 所有的子序列（TODO：标记主函数）
     *
     * @param str 字符串str
     * @return List<String>
     */
    public static List<String> allSubSeq(String str) {
        List<String> ans = new ArrayList<>();
        if (str == null) {
            return ans;
        }
        if (str.length() == 0) {
            ans.add("");
            return ans;
        }
        // 字符串所代表的字符数组
        char[] chs = str.toCharArray();
        process(chs, 0, "", ans);
        return ans;
    }

    /**
     * 收集“字符数组”所表示的字符串的所有子序列。
     * str[0...index-1]的沿途决定，是path记录的，
     * str[index...]每一个字符，都可以选择“要”或者“不要”，
     * 所有的子序列，都放入到ans里面去
     *
     * @param str   字符数组
     * @param index 遍历字符数组时当前来到的索引位置
     * @param path  遍历字符数组时当前索引处的字符要或者不要，所表示的路径（字符串值）
     * @param ans   存放子序列结果的列表
     */
    public static void process(char[] str, int index, String path, List<String> ans) {
        if(index == str.length){
            ans.add(path);
        }else {
            // 不要当前字符
            process(str, index+1, path, ans);
            // 要当前字符
            process(str, index+1, path+String.valueOf(str[index]), ans);
        }
    }


    public static void main(String[] args) {
        String test = "abc";
        List<String> ans = allSubSeq(test);


        for (String str : ans) {
            System.out.println(str);
        }
    }

}
